package source;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Ranges {
    /**
     * 汇总区间
     * 给定一个  无重复元素 的 有序 整数数组 nums 。
     * 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。
     * 也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
     * 列表中的每个区间范围 [a,b] 应该按如下格式输出：
     * "a->b" ，如果 a != b
     * "a" ，如果 a == b
     *
     * @param nums nums 中的所有值都 互不相同，nums 按升序排列
     * @return ["0","2->4","6","8->9"]
     */
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return list;

        int start = nums[0];
        int end = start;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] + 1 != nums[i]) {
                if (start == end) {
                    list.add(String.valueOf(start));
                } else {
                    list.add(start + "->" + end);
                }
                start = nums[i];
            }
            end = nums[i];
        }
        if (start == end) {
            list.add(String.valueOf(start));
        } else {
            list.add(start + "->" + end);
        }

        return list;
    }


    /**
     * 合并区间
     * <p>
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * <p>
     * 示例 1：
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * @param intervals 区间集合
     * @return 合并区间
     */
    public int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        List<int[]> list = new ArrayList<>();
        boolean isNew = true;
        int min = 0, max = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (isNew) {
                min = intervals[i][0];
                max = intervals[i][1];
                isNew = false;
            } else {
                if (max >= intervals[i][0])
                    max = Math.max(max, intervals[i][1]);
                else {
                    list.add(new int[]{min, max});
                    isNew = true;
                    i--;
                }
            }
        }
        list.add(new int[]{min, max});
        return list.toArray(new int[list.size()][]);

    }

    /**
     * 插入区间
     * <p>
     * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，
     * 其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。
     * 同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
     * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，
     * 且区间之间不重叠（如果有必要的话，可以合并区间）。
     * 返回插入之后的 intervals。
     * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
     *
     * @param intervals   intervals = [[1,3],[6,9]]
     * @param newInterval newInterval = [2,5]
     * @return [[1, 5], [6, 9]]
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int index = intervals.length;
        int[][] newArray = new int[index + 1][2];
        int left = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] > newInterval[0]) {
                index = i;
                break;
            }
            newArray[left++] = intervals[i];
        }
        newArray[left++] = newInterval;
        for (int i = index; i < intervals.length; i++) {
            newArray[left++] = intervals[i];
        }
        List<int[]> list = new ArrayList<>();
        int min = 0, max = 0;
        boolean isNew = true;
        for (int i = 0; i < intervals.length + 1; i++) {
            if (isNew) {
                min = newArray[i][0];
                max = newArray[i][1];
                isNew = false;
            } else {
                if (max >= newArray[i][0]) {
                    max = Math.max(max, newArray[i][1]);
                } else {
                    isNew = true;
                    list.add(new int[]{min, max});
                    i--;
                }
            }
        }

        list.add(new int[]{min, max});
        return list.toArray(new int[list.size()][]);
    }

    /**
     * 用最少数量的箭引爆气球
     * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。
     * 墙面上的气球记录在整数数组 points ，
     * 其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
     * <p>
     * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。
     * 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
     * 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。
     * 弓箭一旦被射出之后，可以无限地前进。
     * <p>
     * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
     *
     * @param points points = [[10,16],[2,8],[1,6],[7,12]]
     * @return 2
     */
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int result = 1;
        int right = points[0][1];
        for (int[] point : points) {
            if (point[0] > right) {
                result++;
                right = point[1];
            }
        }
        return result;
    }

    @Test
    public void test2() {
        List<Character> list =new ArrayList<>();
        String s = "hello";

        char[] cs = s.toCharArray();
    }
}
